1. Technical Field
The present invention relates generally to a system for extracting data from an encoded signal transmitted over a noisy signal transmission path, for example a digital subscriber line (DSL). In particular, the invention relates to extracting data from a signal encoded using interleaving and redundancy encoding.
2. Background Information
Many protocols exist for transmitting data over a noisy signal transmission path. Four common techniques employed by these protocols are convolutional encoding, quadrature amplitude modulation (QAM) encoding, interleaving and redundancy encoding.
A convolutional encoder encodes each bit of a data string as a function of the last k bits received, where k is referred to as the constraint length. The convolved data can be decoded, following transmission over the transmission line, using a Viterbi decoder. One form of convolutional encoding is trellis coded modulation (TCM). TCM is ideal to protect against Gaussian noise, but it cannot correct errors due to impulse noise.
A QAM encoder modulates the respective amplitudes of two waves having the same frequency and which are in quadrature (i.e. phase apart), and transmits the sum of the modulated waves. The modulation is performed based on data to be encoded. The modulation typically involves setting each amplitude to one of a predefined set of amplitude values. The resultant wave is described by a constellation diagram, in which each axis of the diagram represents the amplitude of a respective one of the waves following the modulation. The encoded data thus determines which point in the constellation diagram describes the sum of the modulated waves. The resultant waveform (corresponding to one point of the constellation diagram) is referred to as a “carrier symbol”. The decoder receives the transmitted waves, identifies the corresponding point in the constellation diagram, and thereby reconstructs the data.
In redundancy encoding, a first data string having a certain number of bits is transformed into a second data string having a larger number of bits. For example, the second data string may simply be the first data string plus a number of parity bits. The second data string is transmitted over the signal path, and even though it is received with noise, due to the redundancy in the second data string, the first data string can be reconstructed perfectly, provided that the noise is below a critical level. One common technique for redundancy encoding is Reed-Solomon (RS) encoding. A number of data bytes K is transformed into RS coded codeword of N bytes. R is the number of parity bytes added to the data bytes to form the Reed Solomon code, henceN=K+R  (1)
Suppose that the received codeword includes t errors at unknown positions, and f bytes at known positions (so-called “erasures”) which have 50% chance of being errors. A known RS decoder can obtain the correct K bytes, provided that2t+f≦R  (2)
where R can take any of the values 0, 2, 4, 6, 8, 10, 12, 14, 16. That is, the number of errors which can be present in the second data string without preventing the first data string from being recovered, is twice as high in the case that the location of the errors is known.
To take an example, RS encoding is used by the very high bit rate DSL (VDSL) protocol to encode data which will be transmitted over a DSL using discrete multi-tones (DMT) transmission. Suppose that lr is the line rate including overhead in Mbps, and that S is the number of Reed Solomon codewords in one DMT symbol (a “DMT symbol” consists of an amplitude/phase value (i.e. one carrier signal) for each of the tones). Suppose that the DMT symbol rate is 4 kHz (in fact, in VDSL the symbol rate varies according to a “cyclic extension” which appends to the end of each symbol some data from the beginning; according to the size of the cyclic extension the DMT symbol rate ranges from 3.49 kHz to 4.18 kHz). This gives:
                    S        =                                            250              ⁢              lr                                      8              ⁢              N                                .                                    (        3        )            
Interleaving means that a first datastring is transformed into a second data string by re-ordering. The second data string is transmitted over the transmission path. Following the transmission, the first datastring is reconstructed by de-interleaving, which reverses the re-ordering process. If the transmission path includes a noise impulse which corrupts a number of successive bits in the second data string, this noise is distributed over the first data string by the re-ordering process. In particular, interleaving may be combined with RS encoding to ensure that errors are spread over a number of RS codewords.
For example, the interleaver adopted for the protocol VDSL2 is defined by the following rule. Each of I bytes in an interleaver block B0B1 . . . . BI−1 is delayed by an amount that varies linearly with the byte index. This results in a relationship between the input and output given by y(n+Δ[j])=x(n), where j=n mod I, y(n) is defined as the interleaver output and x(n) is the interleaver input with the sequence number n. More precisely, byte Bj (with index j) is delayed by:Δ[j]=(D−1)×j bytes  (4)
where j=0, 1, 2 . . . , I−1, D=MI+1 is the interleaver depth in bytes, I is the interleaver block size in bytes and M is an interleaving depth parameter and D and I are co-prime (i.e. have no common divisor except for 1).
The RS codeword length N is an integer multiple of I, and N=q×I, where q is an integer between 1 and 8 inclusive. All values of q are supported. Codewords are mapped to interleaver blocks such that the first I bytes of the codeword map to the I bytes B0B1 . . . BI−1 of the first interleaver block.
FIG. 1 is a representation of the effect of equation (4) in the case of I=7. I parallel branches (numbered 0 . . . I−1) are implemented with a delay increment of M octets per branch. The interleaver is represented by the left-hand triangular array of boxes each marked M. Each box represents a delay of MI. Thus, the top channel (i.e. the channel along which B0 passes) includes no delay, the next channel a delay of M, the next channel a delay of 2MI, etc. The j-th branch includes a FIFO shift register (delay line) with length j×MI bytes.
The deinterleaver is represented by the right-hand triangular array of boxes. It is similar to the interleaver, but the branch indices are reversed so that the largest interleaver delay corresponds to the smallest deinterleaver delay. Deinterleaver synchronization is achieved by routing the first byte of an interleaved block of I bytes into branch 0.
The total delay of the interleaver/de-interleaver is:({tilde over (D)}1)×(Ĩ1)=MI(I−1) in bytes.  (5)
The interleaver depth is set to meet the requirements for the impulse noise protection and the latency. At any data rate, the minimum latency occurs when the interleaver is turned off.
Denoting the number of bits extracted from the interleaver for each DMT Symbol by Lp,
                    S        =                                            L              p                                      8              ⁢              N                                .                                    (        6        )            
The impulse noise protection (INP) isINP=└(t/2+f)/q┘D bytes  (7)
where t is the error correction capability and f is the erasure decoding capability of RS Coder which together have to satisfy the condition mentioned in equation (2). From equation (7), it can be seen the providing erasure decoding would provide more impulse noise protection without increasing the interleaver delay. However, in fact DSL decoder devices rarely make use of erasure correction because the location of the errors in the received data is rarely known.
US2006/0083324 describes a multi-carrier communication system, such as a DSL based-network, which transmits frames using QAM and convolutional encoding. Frames carry data and some error check bytes for each of a plurality of bit groups in the frame. Following QAM and Trellis decoding, a corrupted frame detector the error check bytes to identify any bytes within the frame which are liable to be erroneous. For each frame of N-bytes, the corrupted frame detector generates an N-byte array containing N decoded bytes and an N-bit array containing a one-bit flag for each of the respective bytes in the N-byte array, indicating whether that byte is suspected of being corrupt. The two sorts of array are passed to respective de-interleaver units. A first (conventional) de-interleaver de-interleaves the N-byte arrays, and an additional de-interleaver de-interleaves the N-bit arrays. The first de-interleaver produces de-interleaved codewords which are then used for RS decoding using the de-interleaved flags to indicate which bytes of the codeword are potentially corrupt. Since the interleaving combines many frames, the de-interleaver units each have to access data from many frames at once. Suppose that the symbols each contain 4 KB of data, a conventional de-interleaver may typically be required to store about 128 KB of data. The additional de-interleaver described in US2006/0083324 would require a memory which stores one bit for every byte stored in the memory of the first de-interleaver, and thus the total de-interleaver memory requirement is increased by 12.5%. This would significantly add to the cost of the device. In another embodiment, the device of US2006/0083324 obtains the corrupt bytes as part of the QAM decoding process instead of using the error check bytes.